package algorithm.MonotonePriorityStack.leetcode_85;

import java.util.Stack;

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int ans = 0;
        int [] height = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
            }
            Stack <Integer> stack = new Stack<>();
            for (int j = 0; j < m; j++) {
                while (!stack.isEmpty() && height[stack.peek()] >= height[j]) {
                    int temp = stack.pop();
                    int left = stack.isEmpty() ? -1 : stack.peek();
                    ans = Math.max(ans, height[temp] * (j - left - 1));
                }
                stack.push(j);
            }
            while (!stack.isEmpty()) {
                int temp = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                ans = Math.max(ans, height[temp] * (m - left - 1));
            }
        }
        return ans;
    }
}